package JZ.JZ26;

/**
 * @author corn
 * @create 2020-08-06-21:54
 */

import java.util.ArrayList;

/**
 * JZ26 二叉搜索树与双向链表
 * 题目描述
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
 */
public class convert {

}
class Solution {
    public TreeNode Convert(TreeNode root)
    {
        if(root==null){
            return null;
        }
        //叶子结点
        if(root.left==null&&root.right==null){
            return root;
        }
        //获取当前结点的左子树
        TreeNode left=Convert(root.left);
        TreeNode p=left;
        //通过循环使得p指向左子树最大的结点。
        while(p!=null&&p.right!=null)
        {
            //获取left的右子树
            p=p.right;
        }
        //左子树不为空，实现与左子树最大的结点互联
        if(left!=null)
        {
            p.right=root;
            root.left=p;
        }
        //获取当前结点的右子树，的最小结点
        TreeNode right=Convert(root.right);
        //右子树不为空
        if(right!=null)
        {
            root.right=right;
            right.left=root;
        }
        return  left!=null ? left : root;
    }
}
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

